import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;

/*
用最大堆保存着k个数
 */
public class E40_2 {
    public static void main(String[] args) {
        int[] array = {4,5,1,6,2,7,3,8};
        ArrayList<Integer> res = GetLeastNumbers_Solution(array, 4);
        System.out.println(res);
    }

    public static ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> res = new ArrayList<>();
        if(k > input.length || k == 0){
            return res;
        }
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(k, new Comparator<Integer>() {//形成降序，保证堆顶为堆里面的最大值
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2.compareTo(o1);
            }
        });

        for(int i = 0; i < input.length; i++){
            if(maxHeap.size() != k){
                maxHeap.add(input[i]);
            }
            else if(maxHeap.peek() > input[i]){
                maxHeap.poll();
                maxHeap.add(input[i]);
            }
        }
        for(int a : maxHeap){
            res.add(a);
        }
        return res;
    }
}
